package com.smh;

import org.junit.jupiter.api.Test;

import java.util.*;

/**
 * @author shiminghui
 * @date 2025/3/15 10:20
 * @description: TODO
 */
public class _046_图_FloydWarShall {

    @Test
    public void test1() {
        Vertex v1 = new Vertex("v1");
        Vertex v2 = new Vertex("v2");
        Vertex v3 = new Vertex("v3");
        Vertex v4 = new Vertex("v4");

        v1.setEdges(List.of(new Edge(v1, v2, 1), new Edge(v1, v3, 1)));
        v2.setEdges(List.of(new Edge(v2, v4, 1)));
        v3.setEdges(List.of(new Edge(v3, v4, 1)));
        v4.setEdges(List.of(new Edge(v4, v1, -2)));
        floydWarshall(List.of(v1, v2, v3, v4));
    }

    public void floydWarshall(List<Vertex> vertexs) {
        int size = vertexs.size();
        int[][] graph = new int[size][size];
        Vertex[][] preArray = new Vertex[size][size];


        // 初始化 garph
        for (int i = 0; i < graph.length; i++) {
            Vertex vertex = vertexs.get(i);
            List<Edge> edges = vertex.getEdges();
            HashMap<Vertex, Integer> map = new HashMap<>();
            if (edges != null) {
                for (Edge edge : edges) {
                    map.put(edge.getTo(), edge.getWeight()); // 顶点到其他顶点的边
                }
            }
            for (int j = 0; j < graph[i].length; j++) {
                if (i == j) {
                    graph[i][j] = 0;
                    continue;
                }

                if (map.containsKey(vertexs.get(j))) {
                    preArray[i][j] = vertex;
                    graph[i][j] = map.get(vertexs.get(j));
                } else {
                    graph[i][j] = Integer.MAX_VALUE;
                }
            }
        }

//        for (int[] ints : graph) {
//            System.out.println(Arrays.toString(ints));
//        }

        // FloydWarshall算法
        for (int k = 0; k < size; k++) {
            for (int i = 0; i < size; i++) {
                if (i == k) {
                    continue;
                }
                int iToK = graph[i][k];
                if (iToK == Integer.MAX_VALUE) {
                    continue;
                }
                for (int j = 0; j < size; j++) {
                    int kToJ = graph[k][j];
                    if (kToJ == Integer.MAX_VALUE) {
                        continue;
                    }
                    if (graph[i][j] > iToK + kToJ) {
                        graph[i][j] = iToK + kToJ;
                        preArray[i][j] = preArray[k][j];
                    }
                }
            }
        }

        // 检测是否出现负环
        for (int i = 0; i < size; i++) {
            if (graph[i][i] < 0) {
                throw new RuntimeException("出现负环");
            }
        }

//        for (int[] ints : graph) {
//            System.out.println(Arrays.toString(ints));
//        }
//        for (Vertex[] vertices : preArray) {
//            for (Vertex vertex : vertices) {
//                System.out.print(vertex+"\t");
//            }
//            System.out.println();
//        }
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                printPath(preArray, vertexs, i, j);
            }
        }
    }

    private void printPath(Vertex[][] preArray, List<Vertex> vertexs, int i, int j) {
        Vertex from = vertexs.get(i);
        Vertex to = vertexs.get(j);
        System.out.print("从" + from.getName() + "到" + to.getName() + "的最短路径为：" + to.getName());

        // 获取该节点的索引
        while (i != j) {
            System.out.print(" <- " + preArray[i][j].getName());
            j = vertexs.indexOf(preArray[i][j]);
        }
        System.out.println();
    }


    private class Vertex {
        private String name;
        private int status;
        private List<Edge> edges;
        private int inDegree; // 入度
        private boolean isVisited; // 是否访问过
        private int distance; // 到该顶点的最短路径
        private Vertex pre; // 记录该顶点的前驱顶点

        { // 初始化
            status = 0;
            distance = Integer.MAX_VALUE;
            isVisited = false;
            inDegree = 0;
        }

        public Vertex(String name) {
            this.name = name;
        }

        public Vertex(String name, List<Edge> edges) {
            this.name = name;
            this.edges = edges;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Vertex vertex = (Vertex) o;
            return status == vertex.status && inDegree == vertex.inDegree && isVisited == vertex.isVisited && distance == vertex.distance && Objects.equals(name, vertex.name) && Objects.equals(edges, vertex.edges) && Objects.equals(pre, vertex.pre);
        }

        @Override
        public int hashCode() {
            return Objects.hash(name);
        }

        public Vertex getPre() {
            return pre;
        }

        public void setPre(Vertex pre) {
            this.pre = pre;
        }

        public boolean isVisited() {
            return isVisited;
        }

        public void setVisited(boolean visited) {
            isVisited = visited;
        }

        public int getDistance() {
            return distance;
        }

        public void setDistance(int distance) {
            this.distance = distance;
        }

        public String getName() {
            return name;
        }

        public void setName(String name) {
            this.name = name;
        }

        public int getStatus() {
            return status;
        }

        public void setStatus(int status) {
            this.status = status;
        }

        public List<Edge> getEdges() {
            return edges;
        }

        public void setEdges(List<Edge> edges) {
            this.edges = edges;
        }

        public int getInDegree() {
            return inDegree;
        }

        public void setInDegree(int inDegree) {
            this.inDegree = inDegree;
        }

        @Override
        public String toString() {
            return "Vertex{" +
                    "name='" + name + '\'' +
                    '}';
        }
    }

    private class Edge {
        private Vertex from;
        private Vertex to;
        private int weight;

        public Edge(Vertex from, Vertex to, int weight) {
            this.from = from;
            this.to = to;
            this.weight = weight;
        }

        public Vertex getFrom() {
            return from;
        }

        public void setFrom(Vertex from) {
            this.from = from;
        }

        public Vertex getTo() {
            return to;
        }

        public void setTo(Vertex to) {
            this.to = to;
        }

        public int getWeight() {
            return weight;
        }

        public void setWeight(int weight) {
            this.weight = weight;
        }
    }
}
